//
//  BinarySearch_15.swift
//  ArithmeticClass15
//
//  Created by xiangzuhua on 2020/11/18.
//

import Foundation

class BinarySearch: NSObject {
    // 非递归二分查找
    class func binarySearch(fromSource arr: [Int], value: Int) -> Int {
        let count = arr.count
        var low = 0
        var height = count - 1
        while low <= height {
            let mid = low + (height - low) / 2
            if arr[mid] == value {
                return mid
            } else if(arr[mid] < value){
                low = mid + 1
            } else {
                height = mid - 1
            }
        }
        return -1
    }

    // 递归二分查找
    class func recursionBinarySearch(fromSource arr: [Int], value: Int) -> Int{
        let height = arr.count - 1
        return recursionBinarySearch(fromSource: arr, value: value, low: 0, height: height)
    }

    class func recursionBinarySearch(fromSource arr: [Int], value: Int, low: Int, height: Int) -> Int{
        if low > height {
            return -1
        }
        let mid = low + (height - low) / 2
        if arr[mid] == value {
            return mid
        } else if(arr[mid] < value){
            return recursionBinarySearch(fromSource: arr, value: value, low: mid + 1 , height: height)
        } else {
            return recursionBinarySearch(fromSource: arr, value: value, low: low, height: mid - 1)
        }
    }
    
    // 通过二分查找，求一个数的平方根，精确到小数点后6位
    class func square(value: Double) -> Double{
        
        if value <= 0 {
            return 0
        }
        if value > 0 && value < 1 {
            var low: Double = 0
            var height: Double = 1
            while low <= height {
                let mid: Double = height - (height - low) * 0.5
                let midString = String(mid)// 获取到String
                let decimalsString = midString.components(separatedBy: ".").last
                var count: Int = 0
                if let decimals = decimalsString {
                    count = decimals.count
                    if count >= 15 {
                        return mid
                    }
                }
                
                if mid * mid == value {
                    return mid
                } else if mid * mid > value{
                    height = mid
                } else {
                    low = mid
                }
            }
            return -1.000000
        } else {
            var low: Double = 0.000000
            var height: Double = value
            while low <= height {
                let mid: Double = low + (height - low) * 0.5
                let midString = String(mid)// 获取到String
                let decimalsString = midString.components(separatedBy: ".").last
                var count: Int = 0
                if let decimals = decimalsString {
                    count = decimals.count
                    if count >= 15 {
                        return mid
                    }
                }
                
                if mid * mid == value {
                    return mid
                } else if mid * mid > value{
                    height = mid
                } else {
                    low = mid
                }
            }
            return -1.000000
        }
    }
}

